package cn.su.day3;

import cn.su.day1.StackCustom;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description: 本测试 求的最小值！
 * 第三题 2021.12.30 生成窗口最大数组
 * 有一个整型数组arr，一个大小为w的窗口从从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
 * 例如：
 * Arr=[4,3,5,4,3,3,6,7]
 * W=3
 * [4,3,5],4,3,3,6,7 窗口最大值为5
 * 4,[3,5,4],3,3,6,7 窗口最大值为5
 * 4,3,[5,4,3],3,6,7 窗口最大值为5
 * 4,3,5,[4,3,3],6,7 窗口最大值为4
 * 4,3,5,4,[3,3,6],7 窗口最大值为6
 * 4,3,5,4,3,[3,6,7] 窗口最大值为7
 * 如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口最大值。
 * 请实现一个函数：
 * 输入：整型数组arr，窗口大小为w。
 * 输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。
 * 上述例子中，res=[5,5,5,4,6,7]
 * 要求：不允许使用时间复杂度为O(N*w)的解法，要求时间复杂度为O(N)
 * 提示：使用双向队列或双向链表实现窗口最大值更新，其中存储的是arr的下标。
 * @author: Sqcode
 * @since: 2022/1/11 14:22
 */
public class Test3 {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{4,3,6,8,4,9};

        int w = 3;

        List<Integer> list = Arrays.asList(arr);
        System.out.println(list);

        List<Integer> result = new ArrayList<>();
        // 有几种组合
        for (int i = 0; i < list.size(); i++) {
            if (list.size() - i >= w) {
                List<Integer> subList = Arrays.asList(arr).subList(i, w + i);
                System.out.println(subList);
                StackCustom stackCustom = new StackCustom(w);
                for (Integer value : subList) {
                    stackCustom.push(value);
                }
                int min = stackCustom.getMin();
                System.out.println(min);
                result.add(min);
            }
        }

        System.out.println("res: " + result);

    }

}